It is common in large database systems, and other computer systems that handle large amounts of multidimensional data, to store indexes and other data structures as arrays of related values. For example, an array can map values contained in or related to one or more objects, such as field values for documents or files, to identifiers of the objects related to or containing those values. As another example, an array can map object identifiers to the field values associated with those objects.
It is common that arrays of this sort are both large and “sparse,” in that there are often many null values. Representing such an array in memory or storage consumes significant memory resources. Thus a variety of techniques have been used to represent sparse arrays. Many sparse array implementations are designed to optimize storage utilization for a specific problem area, not access times.